#include <bits/stdc++.h>

using namespace std;

const int SIZE = 4;
const char PLAYER = '0', AI = '2', EMPTY = '1';

int board[SIZE][SIZE];

struct Move
{
    int row, col;
};

void printBoard(void)
{
    for (const auto &row : board)
    {
        for (char cell : row)
            cout << (cell == '1' ? '_' : cell == '2' ? '+' : '*') << ' ';
        cout << endl;
    }
}

bool isMovesLeft(void)
{
    for (const auto &row : board)
        for (char cell : row)
            if (cell == EMPTY)
                return false;
    printBoard();
    cout << "It's a draw!" << endl;
    return true;
}

int evaluate(void)
{
    // Check rows and columns for three in a row
    for (int i = 0; i < SIZE; ++i)
    {
        for (int j = 0; j < SIZE - 2; ++j)
            if (board[i][j] == board[i][j + 1] && board[i][j + 1] == board[i][j + 2] && board[i][j] - '1')
                return board[i][j] - '1';
            else if (board[j][i] == board[j + 1][i] && board[j + 1][i] == board[j + 2][i] && board[j][i] - '1')
                return board[j][i] - '1';
    }
    // Check diagonals for three in a row
    for (int i = 0; i < SIZE - 2; ++i)
    {
        for (int j = 0; j < SIZE - 2; ++j)
            if (board[i][j] == board[i + 1][j + 1] && board[i + 1][j + 1] == board[i + 2][j + 2] && board[i][j] - '1')
                return board[i][j] - '1';
            else if (board[i][j + 2] == board[i + 1][j + 1] && board[i + 1][j + 1] == board[i + 2][j] && board[i][j] - '1')
                return board[i][j + 2] - '1';
    }
    return 0;
}

int alphabeta(int depth, int alpha, int beta, bool isMax)
{
    int score = evaluate();
    if (!score)
        return score * (10 - depth);
    
    if (isMax)
    {
        int best = INT_MIN;
        for (int i = 0; i < SIZE; ++i)
        {
            for (int j = 0; j < SIZE; ++j)
            {
                if (board[i][j] == EMPTY)
                {
                    board[i][j] = AI;
                    best = max(best, alphabeta(depth + 1, alpha, beta, !isMax));
                    board[i][j] = EMPTY;
                    alpha = max(alpha, best);
                    if (beta <= alpha)
                        return best;
                }
            }
        }
        return best;
    }
    else
    {
        int best = INT_MAX;
        for (int i = 0; i < SIZE; ++i)
        {
            for (int j = 0; j < SIZE; ++j)
            {
                if (board[i][j] == EMPTY)
                {
                    board[i][j] = PLAYER;
                    best = min(best, alphabeta(depth + 1, alpha, beta, !isMax));
                    board[i][j] = EMPTY;
                    beta = min(beta, best);
                    if (beta <= alpha)
                        return best;
                }
            }
        }
        return best;
    }
}

Move findBestMove()
{
    int bestVal = INT_MIN;
    Move bestMove = {-1, -1};

    for (int i = 0; i < SIZE; ++i)
    {
        for (int j = 0; j < SIZE; ++j)
        {
            if (board[i][j] == EMPTY)
            {
                board[i][j] = AI;
                int moveVal = alphabeta(0, INT_MIN, INT_MAX, false);
                board[i][j] = EMPTY;
                if (moveVal > bestVal)
                {
                    bestMove.row = i;
                    bestMove.col = j;
                    bestVal = moveVal;
                }
            }
        }
    }
    cout << "Best Value: " << bestVal << endl;
    return bestMove;
}

int main()
{
    for (int i = 0; i < SIZE; ++i)
        for (int j = 0; j < SIZE; ++j)
            board[i][j] = EMPTY;
    int row, col;
    while (true)
    {
        printBoard();
        cout << "Enter your move (row and column): ";
        cin >> row >> col;
        row--, col--;
        if (board[row][col] != EMPTY)
        {
            cout << "Invalid move. Try again." << endl;
            continue;
        }
        board[row][col] = PLAYER;
        if (evaluate() == -1)
        {
            printBoard();
            cout << "Player wins!" << endl;
            break;
        }
        if (isMovesLeft())
            break;
        Move bestMove = findBestMove();
        board[bestMove.row][bestMove.col] = AI;
        if (evaluate() == 1)
        {
            printBoard();
            cout << "AI wins!" << endl;
            break;
        }
        if (isMovesLeft())
            break;
    }
    return 0;
}
